﻿using System;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.DataStructures.PriorityQueues;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Knapsack.BranchAndBound
{
    public class KnapsackSolver0 : IKnapsackSolver
    {
        protected readonly IList<int> _weights;
        protected readonly IList<double> _values;
        protected readonly int _n;

        #region Inner class

        public class State : IComparable<State>
        {
            public double Score { get; set; }
            public double KnownValue { get; set; }
            public int KnownWeight { get; set; }
            public IList<int> Decisions { get; set; }

            public State(double score, double knownValue, int knownWeight, IList<int> decisions)
            {
                Score = score;
                KnownValue = knownValue;
                KnownWeight = knownWeight;
                Decisions = decisions;
            }

            #region Implementation of IComparable<in State>

            public int CompareTo(State other)
            {
                return Score.CompareTo(other.Score);
            }

            #endregion
        }

        #endregion

        public KnapsackSolver0(IList<int> weights, IList<double> values)
        {
            _values = values;
            _weights = weights;
            _n = _values.Count;
        }

        public virtual IList<int> Solve(int W)
        {
            var item = new State(_values.Sum(), 0.0, 0, new int[] {}.ToAlgoritmiaList());
            var open = new MaxHeap<State>(new[] {item});
            var ramifications = new[] {0, 1};
            IList<int> solution = null;
            double optimalValue = double.NegativeInfinity;
            while (open.Count > 0)
            {
                var s = open.ExtractOptimal();
                foreach(var decision in ramifications )
                {
                    var x = s.Decisions.Concat(new[] {decision}).ToAlgoritmiaList();
                    var knownWeight = s.KnownWeight + decision*_weights[x.Count - 1];
                    var knownValue = s.KnownValue + decision*_values[x.Count - 1];
                    if ( x.Count == _n)
                    {
                        if (knownWeight <= W && knownValue > optimalValue)
                        {
                            solution = x;
                            optimalValue = knownValue;
                        }
                    }
                    else
                    {
                        var weight = knownWeight;
                        var score = knownValue;
                        for(int i = x.Count; i < _n; i++)
                        {
                            if ( weight + _weights[i] <= W)
                            {
                                weight += _weights[i];
                                score += _values[i];
                            }
                        }
                        if ( knownWeight <= W)
                        {
                            open.Add(new State(score,knownValue,knownWeight,x));
                        }
                    }
                }
            }
            return solution;
        }

    }
}
